package leetCode.fourthWeek;

import java.util.LinkedList;
import java.util.List;

public class Code_85 {
  public int maximalRectangle(char[][] matrix) {
    int max = 0;
    if (matrix.length == 0) {
      return 0;
    }
    for (int i = 0; i < matrix.length; i++) {
      List<Integer> tmp = new LinkedList<>();
      for (int j = 0; j < matrix[i].length; j++) {
        int height = 0;
        for (int k = i; k >= 0; k--) {
          if (matrix[k][j] == '0') {
            break;
          }
          if (matrix[k][j] == '1') {
            height++;
          }
        }
        tmp.add(height);
      }
      max = MaxRect(tmp) > max ? MaxRect(tmp) : max;
    }
    return max;
  }

  public int MaxRect(List<Integer> tmp) {
    int MAX = Integer.MIN_VALUE;
    for (int i = 0; i < tmp.size(); i++) {
      if (tmp.get(i) == 0) {
        continue;
      }
      int left = i, right = i; // 左右指针
      while (left >= 0 && tmp.get(left) >= tmp.get(i)) {
        left--;
      }
      while (right < tmp.size() && tmp.get(right) >= tmp.get(i)) {
        right++;
      }
      if (tmp.get(i) * (right - left - 1) > MAX) {
        MAX = tmp.get(i) * (right - left - 1);
      }
    }
    return MAX;
  }
}
